package com.platform.modules.alg.alglib.hdu2568;

public class Hdu2568 {
    private final int maxn = 40005;
    // n 个结点
    private int n;
    // m 个查询
    int m;
    int k;
    // F(i,j) 表示 i 向上走 2^j 步的结点
    int F[][] = new int[maxn][20];
    // 头结点
    int head[] = new int[maxn];
    // 距离
    int dist[] = new int[maxn];
    // 深度数组
    int d[] = new int[maxn];
    int cnt;
    Edge e[] = new Edge[maxn << 1];
    public String output = "";

    public Hdu2568() {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    void add(int u, int v, int w) {
        e[++cnt].to = v;
        e[cnt].c = w;
        e[cnt].next = head[u];
        head[u] = cnt;
    }

    // 求深度、距离、初始化F[v][0]
    void dfs(int u) {
        for (int i = head[u]; i > 0; i = e[i].next) {
            int v = e[i].to;
            if (v == F[u][0])
                continue;
            d[v] = d[u] + 1; // 深度
            dist[v] = dist[u] + e[i].c; // 距离
            F[v][0] = u; // F[v][0]存v的父节点
            dfs(v);
        }
    }

    // 构造 ST 表
    void ST_create() {
        for (int j = 1; j <= k; j++)
            for (int i = 1; i <= n; i++) // i 先走 2^(j-1) 步到达 F[i][j-1],再走 2^(j-1) 步
                F[i][j] = F[F[i][j - 1]][j - 1];
    }

    int LCA_st_query(int x, int y) // 求区间 x,y 的最近公共祖先
    {
        // 保证 x 的深度小于等于 y
        if (d[x] > d[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        // y 向上走到与 x 同一深度
        for (int i = k; i >= 0; i--)
            if (d[F[y][i]] >= d[x])
                y = F[y][i];
        if (x == y)
            return x;
        for (int i = k; i >= 0; i--) // x,y 一起向上走
            if (F[x][i] != F[y][i]) {
                x = F[x][i];
                y = F[y][i];
            }
        return F[x][0]; // 返回 x 的父亲
    }

    public String cal(String input) {
        int a, b, lca;
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);

        k = (int) Math.floor(Math.log(n) / Math.log(2));
        for (int i = 1; i <= n; i++) // 初始化
            head[i] = d[i] = dist[i] = 0;
        cnt = 0;
        for (int i = 1; i < n; i++) // 输入一棵树的 n-1 边
        {
            int x, y, z;
            String[] info = line[i].split(" ");
            x = Integer.parseInt(info[0]);
            y = Integer.parseInt(info[1]);
            z = Integer.parseInt(info[2]);
            add(x, y, z);
            add(y, x, z);
        }
        d[1] = 1;
        dfs(1);
        ST_create(); // 创建 ST 表
        for (int i = 1; i <= m; i++) {
            String[] query = line[n - 1 + i].split(" ");
            a = Integer.parseInt(query[0]);
            b = Integer.parseInt(query[1]);
            lca = LCA_st_query(a, b);
            output += dist[a] + dist[b] - 2 * dist[lca] + "\n";
        }
        return output;
    }
}

class Edge {
    public int to;
    public int c;
    public int next;
}
